/*
 * Copyright (C), 2015-2018
 * FileName: Solution062
 * Author:   zhao
 * Date:     2018/12/13 20:39
 * Description: 62. 不同路径
 * History:
 * <author>          <time>          <version>          <desc>
 * 作者姓名           修改时间           版本号              描述
 */
package com.lizhaoblog.mid;

import java.util.HashMap;

/**
 * 〈一句话功能简述〉<br>
 * 〈62. 不同路径〉
 *
 * @author zhao
 * @date 2018/12/13 20:39
 * @since 1.0.0
 */
public class Solution062 {
  /**************************************
   * 题目
   一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。

   机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。

   问总共有多少条不同的路径？



   例如，上图是一个7 x 3 的网格。有多少可能的路径？

   说明：m 和 n 的值均不超过 100。

   示例 1:

   输入: m = 3, n = 2
   输出: 3
   解释:
   从左上角开始，总共有 3 条路径可以到达右下角。
   1. 向右 -> 向右 -> 向下
   2. 向右 -> 向下 -> 向右
   3. 向下 -> 向右 -> 向右
   示例 2:

   输入: m = 7, n = 3
   输出: 28
   **************************************/

  /*************************************
   想法：
   和第70题走楼梯类似，不过这个是二维的，那个是直线的
   任何一格位置数据都是通过 他左边一格的数据+上边的数据来的。
   比如(7,3)坐标的数据，是通过(6,3) + (7,2)获取到的结果
   那么同理可得(6,3)又是根据(5,3)+(6,2)来的，
   同理可得(7,2)又是根据(7,1)+(6,2)来的，
   这样就能往前推到(1,1)了，这里就是边界条件
   这里注意一下，(6,3)和(7,2)都用到了(6,2)的结果，如果每次都去计算(6,2)的值，很浪费时间，
   所以我们用一个hashMap保存数据，key就是(6,2)，value就是(6,2)的值

   我的做法
   超过5.74%的测试案例

   时间复杂度/空间复杂度：  n/n
   代码执行过程：

   总结：

   ************************************/
  HashMap hashMap = new HashMap<String, Integer>();

  public int uniquePaths(int m, int n) {
    return recuResult(m, n);
  }

  public int recuResult(int m, int n) {
    int result = 0;
    if (m == 0 || n == 0) {
      return 0;
    }

    if (m == 1 && n == 1) {
      return 1;
    }

    if (hashMap.get(m + "+" + n) != null) {
      return (Integer) hashMap.get(m + "+" + n);
    }

    result = recuResult(m - 1, n) + recuResult(m, n - 1);
    hashMap.put(m + "+" + n, result);
    return result;
  }

  /**************************************
   * 比我好的答案 better
   * 这个直接用数组求解，速度比我快
   * ***********************************/
  public int better(int m, int n) {
    if (m <= 0 || n <= 0) {
      return 0;
    }
    int[][] dp = new int[m][n];
    dp[0][0] = 1;
    for (int i = 1; i < n; i++) {
      dp[0][i] = 1;
    }
    for (int i = 1; i < m; i++) {
      dp[i][0] = 1;
    }
    for (int i = 1; i < m; i++) {
      for (int j = 1; j < n; j++) {
        dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
      }
    }
    return dp[m - 1][n - 1];
  }
}